//
//	  LinkedList.java
//
//	  Copyright (c) 2011 <John Lawniczak>
//	  jlawniczak340license@gmail.com
//
//    This file is part of CS102_Assignment3.
//
//    CS102_Assignment3 is free software: you can redistribute it and/or modify
//    it under the terms of the GNU General Public License as published by
//    the Free Software Foundation, version 3 of the License.
//
//    CS102_Assignment3 is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//    GNU General Public License for more details.
//
//    You should have received a copy of the GNU General Public License
//    along with CS102_Assignment3.  If not, see <http://www.gnu.org/licenses/>.
//
/**************************************************
Class Name:LinkedList
Author's Name:John Lawniczak
Date:05-05-2010
Description of the class: generic type linkedlist of
 	nodes with ability to add, replace, remove etc
***************************************/


public class LinkedList <t>{
	
	private Node<t> head, tail, curr;
	private int listCount =0;
	
	public LinkedList(){
		head = null;
		curr = head;
	}
	/**************************************************
	Method name: addLast
	Input to the method: t element to add the end of the linked list
	Output(Return value): none
	Brief Description: adds an new node to the end of the list  
	Author: John Lawniczak
	**************************************************/
	public void addLast(t n){
		boolean first = false;
		curr = head;
		if(curr == null){
			curr = new Node<t>(n);
			head = curr;
			first = true;
		}
		while(!first&&curr.getNext()!=null){
			curr = curr.getNext();
		}
		if(!first)
			curr.setNext(new Node<t>(n));
		tail = curr;
		listCount++;
	}
	
	/**************************************************
	Method name: addFirst
	Input to the method: t element to add the beginning of the linked list
	Output(Return value): none
	Brief Description: adds an new node to the beginning of the list  
	Author: John Lawniczak
	**************************************************/	
	public void addFirst(t n){
		if(head == null){
			head = new Node<t>(n);
			curr = head;
		}else{
			//System.out.println("gere:");
			Node <t> tmpHead = new Node<t>(n);
			tmpHead.setNext(head);
			head = tmpHead;
		}
		listCount++;
	}
	
	/**************************************************
	Method name: add
	Input to the method: t element to add and index to add it to
	Output(Return value): none
	Brief Description: adds an new node at an index  
	Author: John Lawniczak
	**************************************************/
	public void add ( int index, t n){
		curr = head;
		Node<t> temp = new Node<t>(n);
		if(index >= listCount){
			this.addLast(n);
		}else if(index==0){
			this.addFirst(n);
		}else{
			for(int i = 1; i < index && curr.getNext() != null; i++)
			{
				curr = curr.getNext();
			}
			// set the new node's next-node reference to this node's next-node reference
			temp.setNext(curr.getNext());
			// now set this node's next-node reference to the new node
			curr.setNext(temp);
			listCount++;// increment the number of elements variable
		}
		
	}
	
	/**************************************************
	Method name: contains
	Input to the method: t element look for in the linked list
	Output(Return value): int the index of the first occurence of the element
	Brief Description: finds the index of the first instance of the input
	Author: John Lawniczak
	**************************************************/
	public int contains (t elem){
		curr = head;
		boolean found = false;
		int i;
		for(i =1; i<=listCount && !found;i++ ){
			if(curr.getElement().equals(elem)){
				found = true;
			}else{
				curr = curr.getNext();
			}
		}
		if(found){
			return i-1;
		}else{
			return -1;
		}
	}
	
	/**************************************************
	Method name: getCurr
	Input to the method: none
	Output(Return value): t the current element
	Brief Description: returns the element currently selected  
	Author: John Lawniczak
	**************************************************/
	public t getCurr(){
		return curr.getElement();
	}

	/**************************************************
	Method name: get
	Input to the method: index to get
	Output(Return value): t the  element
	Brief Description: returns the element at the index  
	Author: John Lawniczak
	**************************************************/
	public t get(int index) throws IndexOutOfBoundsException{
		curr = head;
		if(index>listCount){
			throw new IndexOutOfBoundsException();
		}else{
			for(int i =1; i<index; i++){
				curr = curr.getNext();
			}
		}
		return curr.getElement();
	}
	
	/**************************************************
	Method name: getFirst
	Input to the method: none
	Output(Return value): t the first element
	Brief Description: returns the first element  
	Author: John Lawniczak
	**************************************************/
	public t getFirst(){
		return head.getElement();
	}

	/**************************************************
	Method name: getLast
	Input to the method: none
	Output(Return value): t the last element
	Brief Description: returns the last element  
	Author: John Lawniczak
	**************************************************/
	public t getLast(){
		return tail.getElement();
	}
	
	/**************************************************
	Method name: size
	Input to the method: none
	Output(Return value):  int the size of the list
	Brief Description: returns the size of the list  
	Author: John Lawniczak
	**************************************************/
	public int size(){
		return listCount;
	}
	
	/**************************************************
	Method name: remove
	Input to the method: index to remove
	Output(Return value): t the element removed
	Brief Description: removes the element at the index and returns it  
	Author: John Lawniczak
	**************************************************/
	public t remove(int index){
		curr = head;
		t ret = null;
		if(index>listCount || index<0){
			throw new IndexOutOfBoundsException();
		}else if(index == 1){
			removeFirst();
		}else if(index == listCount){
			removeLast();
		}else{
			Node<t> prev= head;
	        if (index != 0){
	        	curr = head.getNext();
   	            for (int count = 1; count < index-1; count++){
   	            	prev = curr;
   	            	curr = curr.getNext();
   	            }
   	         }
   	         ret = curr.getElement();
   	         prev.setNext(curr.getNext());
   			listCount--;
   			curr = head;
		}
		return ret;
	}
	
	/**************************************************
	Method name: removeFirst
	Input to the method: none
	Output(Return value): t the element removed
	Brief Description: removes the element at the beginning and returns it  
	Author: John Lawniczak
	**************************************************/	
	public t removeFirst(){
		t ret = null;
		if(head != null){
			ret = head.getElement();
			head = head.getNext();
		}
		listCount--;
		return ret;
	}
	/**************************************************
	Method name: removeLast
	Input to the method: none
	Output(Return value): t the element removed
	Brief Description: removes the last element and returns it  
	Author: John Lawniczak
	**************************************************/
	public t removeLast(){
		t ret =null;
		curr = head;
		Node<t> prev = null;
		if(listCount==1){
			head = null;
			listCount--;
		}else{
			for(int i =0; curr.getNext()!=null;i++){
				prev = curr;
				curr = curr.getNext();
			}
			prev.setNext(null);
			ret = prev.getElement();
			tail = prev;
			listCount--;

		}
		return ret;
	}
	
	/**************************************************
	Method name: toString
	Input to the method: none
	Output(Return value): String the string representing the list
	Brief Description: converts the list to a string to be printed  
	Author: John Lawniczak
	**************************************************/
	public String toString(){
		curr = head;
		String ret = "";
		while(curr!=null){
			//System.out.println("cur element:" + curr.getElement());
			ret = ret + curr.getElement().toString() + " "; 
			curr = (curr.getNext());
		}
		return ret;
	}
	
	/**************************************************
	Method name: empty
	Input to the method: none
	Output(Return value): none
	Brief Description: empties the list  
	Author: John Lawniczak
	**************************************************/
	public void empty(){
		head = null;
	}
	
}
